package arithmetic2.day02;

import java.util.Arrays;

/*
    由快速排序演变而来的问题
    荷兰国旗问题:
        给定一个数组和一个num,将数组中小于等于num的数放在数组的左边，大于num的数放在num的右边
 */
public class Demo02 {
    public static void main(String[] args) {
//        int arr[] = new int[]{3,6,8,3,1,2,0};

        int arr[] = new int[]{0,1,2,3,3,8,6};

        partition3(arr,5,6,8);

        System.out.println(Arrays.toString(arr));
    }

    //划分算法  index是num所在的索引
    public static void partition(int arr[],int start,int end,int index){
        if(start < end){
            int i = start;
            int j = end;
            int temp = arr[index];
            while (i!=j){
                while (arr[j]>temp && i<j){
                    j--;
                }
                arr[i] = arr[j];
                while (arr[i]<=temp && i<j){
                    i++;
                }
                arr[j] = arr[i];
            }
            arr[i] = temp;
        }
    }

    //划分算法,将数组中小于等于key的数放在数组左边，大于key的数放在数组的右边
    public static void partition1(int arr[],int key){
        int i = -1;  //小于等于区域的最大索引,左边索引的数都是小于等于key的
        for(int k=0;k<arr.length;k++){
            if(arr[k]<=key){    //当前数<=key，将当前数与小于等于区域的下一个数交换，小于等于区域右扩1个 k++
                swap(arr,k,i+1);
                i++;
            }else { //当前数>key k++

            }
        }
    }

    //划分算法，将数组中小于key的数放在数组左边，等于key的数放在数组中间，大于key的数放在数组右边
    public static void partition2(int arr[],int key){
        int i = -1;  //小于等区域的最大索引,左边索引的数都是小于key的
        int j = arr.length; //大于区域的最小索引，右边的数都是大于key的
        //遍历当前数组
        for(int k=0;k<arr.length && j>k;k++){
            if(arr[k]<key){    //当前数<key，将当前数与小于等于区域的下一个数交换，小于区域右扩1个 k++
                swap(arr,k,i+1);
                i++;
            }else if(arr[k]>key){  //当前数>key 将当前数与大于区的前一个数交换，大于区左扩,k不变
                swap(arr,k,j-1);
                j--;
                k--;
            }else { //当前数=key k++

            }
        }
    }

    //将数组划分为三段,左边全是小于某个数的，中间是等于某个数的，右边全是大于某个数的
    public static int[] partition3(int arr[],int start,int end,int key){
        int i = start-1;  //小于等区域的最大索引,左边索引的数都是小于key的
        int j = end+1; //大于区域的最小索引，右边的数都是大于key的
        //遍历当前数组
        for(int k=start;k<=end && j>k;k++){
            if(arr[k]<key){    //当前数<key，将当前数与小于等于区域的下一个数交换，小于区域右扩1个 k++
                swap(arr,k,i+1);
                i++;
            }else if(arr[k]>key){  //当前数>key 将当前数与大于区的前一个数交换，大于区左扩,k不变
                swap(arr,k,j-1);
                j--;
                k--;
            }
        }
        return new int[]{i+1,j-1};
    }

    //交换两个数
    public static void swap(int arr[],int i,int j){
        int temp =  arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
